#include    "regex.h"
#include    <stdlib.h>
#include    <string.h>

#ifdef	DEBUG
#include    <assert.h>
#include    <stdio.h>
#endif

typedef int TOKEN_TYPE;
#define TOKEN_CHAR 0x0001
#define TOKEN_LBRACKET 0x0002
#define TOKEN_RBRACKET 0x0004
#define TOKEN_SQUARE_LBRACKET 0x0008
#define TOKEN_SQUARE_RBRACKET 0x0010

#define TOKEN_ASTERISK 0x0020
#define TOKEN_PLUS 0x0040
#define TOKEN_QUESTION 0x0080
#define TOKEN_REPEAT 0x0100

#define TOKEN_ERROR 0x0000
#define TOKEN_COMPLETE 0x0200

static struct translate* alloc_translate(struct nfa_stat *from,
		struct nfa_stat *to,
		TRAN_TYPE type,
		unsigned char lo,
		unsigned char hi)
{
#ifdef DEBUG
	static index = 0;
#endif
	struct translate *p;
	p = malloc(sizeof(struct translate));
	if( p == NULL )
		return NULL;
#ifdef 	DEBUG
	p->id = index;
	index++;
#endif
	p->type = type;
	p->lo = lo;
	p->hi = hi;
	p->link.next = &p->link;
	p->link.prev = &p->link;
	list_insert_after(&p->link,&from->translates);
	p->stat = to;
	return p;
}

static struct nfa_stat* alloc_nfa_stat(struct nfa* nfa)
{
#ifdef DEBUG
	static index = 0;
#endif
	struct nfa_stat *p = malloc(sizeof(struct nfa_stat));
	if( p == NULL )
		return NULL;
	p->translates.next = &p->translates;
	p->translates.prev = &p->translates;
	p->final = 0;
#ifdef DEBUG
	p->id = index;
	index++;
#endif
	if( nfa->start == NULL )
	{
		nfa->start = p;
		p->link.next = &p->link;
		p->link.prev = &p->link;
	}
	else
	{
		list_insert_before(&p->link,&nfa->start->link);
	}
	return p;
}

static struct nfa* alloc_nfa()
{
	struct nfa* nfa;
	nfa = malloc(sizeof(struct nfa));
	if( nfa == NULL )
		return NULL;
	nfa->start = NULL;
	return nfa;
}
struct stack
{
	struct list link;
	struct nfa_stat *stat;
	char type;
};

static void stack_init(struct stack *stack)
{
	stack->link.next = &stack->link;
	stack->link.prev = &stack->link;
}

static int stack_push(struct nfa_stat *stat,char type,struct stack *stack)
{
	struct stack *node;
	node = malloc(sizeof(struct stack));
	if( node == NULL )
		return -1;
	list_insert_after(&node->link,&stack->link);
	node->stat = stat;
	node->type = type;
	return 0;
}

static struct stack* stack_pop(struct stack *stack)
{
	struct list* p;
	p = stack->link.next;
	if(p == &stack->link)
		return NULL;
	list_delete(p);
	return container_of(p,struct stack,link);
}

enum stat_mathine
{
	s0=0,s1,s2,s3,s4,s5,s6,s7,s8,s9,s10,s11,s12,s13,s14
};
TOKEN_TYPE get_token(char *str,int *len,char *returnchar)
{
	enum stat_mathine stat = s0;

	*len = 0;
	while( 1 )
	{
		if( stat == s0 )
		{
			switch ( str[*len] )
			{
				case '*' :
				case '+' :
				case '?' :
				case '{' :
				case '}' :
					++(*len);
					return TOKEN_ERROR;
				case '(' :
					++(*len);
					return TOKEN_LBRACKET;
				case ')' :
					++(*len);
					stat = s4;
					break;
				case ']' :
					++(*len);
					stat = s5;
					break;
				case '[' :
					++(*len);
					return TOKEN_SQUARE_LBRACKET;

				case '\\' :
					stat = s1;
					++(*len);
					break;
				case '\0' :
					return TOKEN_COMPLETE;
				default :
					*returnchar = str[0];
					stat = s2;
					++(*len);
					break;
			}
		}
		else if(stat == s1)
		{
			switch ( str[*len] )
			{
				case '*' :
				case '+' :
				case '?' :
				case '{' :
				case '}' :
				case '[' :
				case ']' :
				case '(' :
				case ')' :
				case '\\' :
					*returnchar = str[1];
					++(*len);
					stat = s2;
					break;
				default :
					return TOKEN_ERROR;
			}

		}
		else if(stat == s2)
		{
			switch ( str[*len] )
			{
				case '*' :
					++(*len);
					return TOKEN_CHAR | TOKEN_ASTERISK;
				case '+' :
					++(*len);
					return TOKEN_CHAR | TOKEN_PLUS;
				case '?' :
					++(*len);
					return TOKEN_CHAR | TOKEN_QUESTION;
				case '\\' :
					++(*len);
					stat = s3;
					break;
				case '}' :
					++(*len);
					return TOKEN_CHAR | TOKEN_REPEAT;
				default :
					return TOKEN_CHAR;
			}
		}
		else if(stat == s3)
		{
			switch ( str[*len] )
			{
				case '*' :
				case '+' :
				case '?' :
				case '{' :
				case '}' :
				case '[' :
				case ']' :
				case '(' :
				case ')' :
				case '\\' :
					--(*len);
					return TOKEN_CHAR;
				default :
					return TOKEN_ERROR;
			}
		}
		else if(stat == s4)
		{
			switch ( str[*len] )
			{
				case '*' :
					++(*len);
					return TOKEN_RBRACKET | TOKEN_ASTERISK;
				case '+' :
					++(*len);
					return TOKEN_RBRACKET | TOKEN_PLUS;
				case '?' :
					++(*len);
					return TOKEN_RBRACKET | TOKEN_QUESTION;
				default :
					return TOKEN_RBRACKET;
			}
		}
		else if(stat == s5)
		{
			switch ( str[*len] )
			{
				case '*' :
					++(*len);
					return TOKEN_SQUARE_RBRACKET |  TOKEN_ASTERISK;
				case '+' :
					++(*len);
					return TOKEN_SQUARE_RBRACKET | TOKEN_PLUS;
				case '?' :
					++(*len);
					return TOKEN_SQUARE_RBRACKET | TOKEN_QUESTION;
				default :
					return TOKEN_SQUARE_RBRACKET;
			}
		}
	}
}

static TOKEN_TYPE __nfa_compile(struct nfa_stat* start,
		struct nfa_stat **end,
		char *str,
		struct nfa *nfa,
		int mode,
		int *len)
{
	TOKEN_TYPE type;
	struct nfa_stat *curstat = start;
	struct nfa_stat *p;
	struct nfa_stat *subend;
	TOKEN_TYPE subtype;
	char *substr;
	int tokenlen = 0;
	int sublen = 0;
	char c;

	*len = 0;
	while((type = get_token(str,&tokenlen,&c)) != TOKEN_COMPLETE )
	{
		(*len) += tokenlen;
		if( mode == 0 )
		{
			switch ( type )
			{
				case TOKEN_CHAR:
					p = alloc_nfa_stat(nfa);
					if( p == NULL )
						goto mem_error;

					if(alloc_translate(curstat,p,TRAN_CHAR,c,c) == NULL)
						goto mem_error;

					curstat = p;
					break;
				case TOKEN_CHAR | TOKEN_ASTERISK :
					if(alloc_translate(curstat,curstat,TRAN_CHAR,c,c) == NULL)
						goto mem_error;
					break;
				case TOKEN_CHAR|TOKEN_QUESTION :
					p = alloc_nfa_stat(nfa);
					if( p == NULL )
						goto mem_error;

					if(alloc_translate(curstat,p,TRAN_CHAR,c,c) == NULL)
						goto mem_error;
					if(alloc_translate(curstat,p,TRAN_FREE,'?','?') == NULL)
						goto mem_error;

					curstat = p;
					break;
				case TOKEN_CHAR | TOKEN_PLUS :
					p = alloc_nfa_stat(nfa);
					if( p == NULL )
						goto mem_error;

					if( alloc_translate(curstat,p,TRAN_CHAR,c,c) == NULL)
						goto mem_error;
					if (alloc_translate(p,p,TRAN_CHAR,c,c) == NULL)
						goto mem_error;

					curstat = p;
					break;
				case TOKEN_LBRACKET :
					str += tokenlen;
					subtype = __nfa_compile(curstat,&subend,str,nfa,0,&sublen);
					switch ( subtype )
					{
						case TOKEN_RBRACKET :
							curstat = subend;
							break;
						case TOKEN_RBRACKET|TOKEN_ASTERISK :
							if(alloc_translate(subend,curstat,TRAN_FREE,'*','*') == NULL)
								goto mem_error;
							break;
						case TOKEN_RBRACKET|TOKEN_QUESTION :
							if( alloc_translate(curstat,subend,TRAN_FREE,'?','?') == NULL )
								goto mem_error;
							curstat = subend;
							break;
						case TOKEN_RBRACKET|TOKEN_PLUS :
							curstat = subend;
							__nfa_compile(curstat,&subend,str,nfa,0,&sublen);
							if( alloc_translate(subend,curstat,TRAN_FREE,'+','+') == NULL )
								goto mem_error;
							break;
						default :
							goto mem_error;
					}
					tokenlen = sublen;
					break;
				case TOKEN_RBRACKET :
				case TOKEN_RBRACKET|TOKEN_ASTERISK :
				case TOKEN_RBRACKET|TOKEN_QUESTION :
				case TOKEN_RBRACKET|TOKEN_PLUS :
					(*end) = curstat;
					return type;
				default :
					goto mem_error;
			}
		}
		else
		{
		}
		str += tokenlen;
	}
	*end = curstat;
	return type;

mem_error:
	return TOKEN_ERROR;
}
struct nfa* nfa_compile(char *pattern)
{
	struct nfa *nfa;
	struct nfa_stat *start;
	struct nfa_stat *end;
	int len;

	nfa = alloc_nfa();
	if( nfa == NULL )
		goto exit;

	start = alloc_nfa_stat(nfa);
	if( start == NULL )
		goto mem_error;

	if(__nfa_compile(start,&end,pattern,nfa,0,&len) == TOKEN_ERROR)
		goto compile_error;

	end->final = 1;
	return nfa;

compile_error:
	free(start);
mem_error:
	free(nfa);
exit:
	return NULL;
}

/*
   struct nfa* nfa_compile(const char *pattern,int len)
   {
   struct nfa *nfa;
   char c;
   int i = 0;
   struct translate *trans;
   struct nfa_stat *curstat;
   struct nfa_stat *prestat = NULL;
   struct nfa_stat *prebracketstat = NULL;
   struct nfa_stat *p;
   struct stack stack;
   struct stack *pstack;
   TOKEN_TYPE last_token;

   stack_init(&stack);
   nfa = alloc_nfa();
   if( nfa == NULL )
   return NULL;

   curstat = alloc_nfa_stat(nfa);
   if( curstat == NULL )
   goto mem_error;

   while( i < len )
   {
   c = pattern[i];
   switch ( c )
   {
   case ')' :
   if(last_token == TOKEN_ESCAPE)
   goto normal_char;
   pstack = stack_pop(&stack);
   if( pstack == NULL )
   goto out_of_stack_mem;
   if( pstack->type != '(' )
   goto out_of_stack_mem;
   prebracketstat = pstack->stat;
   free(pstack);
   last_token = TOKEN_RBRACKET;
   break;
   case '(' :
   if(last_token == TOKEN_ESCAPE)
   goto normal_char;
   if(stack_push(curstat,'(',&stack) != 0)
   goto out_of_stack_mem;
   last_token = TOKEN_LBRACKET;
   break;
   case '\\' :
   if(last_token == TOKEN_ESCAPE)
   goto normal_char;
   last_token = TOKEN_ESCAPE;
   break;
   case '+' :
   if( last_token == TOKEN_ESCAPE )
   goto normal_char;
   if(last_token == TOKEN_RBRACKET)
   {
   p = prebracketstat;
   }
   else
   {
   p = prestat;
   }
   alloc_translate(curstat,p,TRAN_FREE,'+','+');
   last_token = TOKEN_CHAR;
   break;
   case '*' :
   if( last_token == TOKEN_ESCAPE )
   goto normal_char;
   if(last_token == TOKEN_RBRACKET)
{
	p = prebracketstat;
}
else
{
	p = prestat;
}
alloc_translate(curstat,p,TRAN_FREE,'*','*');
prestat = curstat;
curstat = p;
last_token = TOKEN_CHAR;
break;
case '?' :
if(last_token == TOKEN_ESCAPE)
	goto normal_char;
if(last_token == TOKEN_RBRACKET)
{
	p = prebracketstat;
}
else
{
	p = prestat;
}
alloc_translate(p,curstat,TRAN_FREE,'?','?');
last_token = TOKEN_CHAR;
break;
case '.' :
if( last_token == TOKEN_ESCAPE )
	goto normal_char;
	p = alloc_nfa_stat(nfa);
if( p == NULL )
	goto mem_error;
	trans = alloc_translate(curstat,p,TRAN_ANY,(unsigned char)0,(unsigned char)255);
if( trans == NULL )
	goto mem_error;
	prestat = curstat;
	curstat = p;
	last_token = TOKEN_CHAR;
	break;
	case '^' :
if( last_token == TOKEN_ESCAPE )
	goto normal_char;
	break;
	default :
if( last_token == TOKEN_ESCAPE )
{
	switch ( c )
	{
		case 'n' :
			c = '\n';
			break;
		case 't' :
			c = '\t';
			break;
		default :
			goto out_of_stack_mem;
	}
}
normal_char:
p = alloc_nfa_stat(nfa);
if( p == NULL )
	goto mem_error;

	trans = alloc_translate(curstat,p,TRAN_CHAR,c,c);
if( trans == NULL )
	goto mem_error;

	prestat = curstat;
	curstat = p;
	last_token = TOKEN_CHAR;
	break;
	}
i++;
}
if(stack.link.next != &stack.link)
	goto out_of_stack_mem;
	curstat->final = 1;
	return nfa;
out_of_stack_mem:
//free brack_stack
mem_error:

if(nfa)
{
	if(nfa->start)
	{
		foreach_stat_in_nfa()
		{
			foreach_translate_in_stat()
			{
				free_translate();
			}
		}
		free_stat();
	}
	free_nfa();
}

return NULL;
}
*/
#ifdef DEBUG
void nfa_printf(struct nfa* nfa)
{
	struct list *p,*q;
	assert(nfa);
	printf("-----------debug message of nfa-------------\n");
	if(nfa->start)
	{
		p = &nfa->start->link;
		do
		{
			if( container_of(p,struct nfa_stat,link)->final != 0 )
			{
				printf("final ");
			}
			printf("stat id:%d\n",(container_of(p,struct nfa_stat,link))->id);

			q = (container_of(p,struct nfa_stat,link))->translates.next;
			while( q != &((container_of(p,struct nfa_stat,link))->translates) )
			{
				printf("\ttrans id:%d,stat:%d,char %c->%c\n",
						(container_of(q,struct translate,link))->id,
						(container_of(q,struct translate,link))->stat->id,
						(container_of(q,struct translate,link))->lo,
						(container_of(q,struct translate,link))->hi);
				q = q->next;
			}

			p = p->next;
		}
		while( p != &nfa->start->link );
	}
}
#endif

static int add_nfa_set(struct nfa_stat *stat,struct nfa_stat_set *set)
{
	struct nfa_stat_set_node *node;
	struct nfa_stat_set_node *entry;
	struct list *p;
	node = malloc(sizeof(struct nfa_stat_set_node));
	if( node == NULL )
		return -1;
	node->stat = stat;

	p = set->head.next;
	while( p != &set->head )
	{
		entry = container_of(p,struct nfa_stat_set_node,link);
		if( entry->stat == node->stat )
		{
			free(node);
			return 0;
		}
		if( entry->stat > node->stat )
			break;
		p = p->next;
	}
	list_insert_before(&node->link,p);

	if( stat->final == 1 )
		set->final = 1;
	else 
		set->final = 0;
	set->num++;

	return 0;
}

static struct dfa_stat* alloc_dfa_stat(struct nfa_stat_set *set,struct dfa *dfa)
{
#ifdef DEBUG
	static int id = 0;
#endif
	struct dfa_stat *ret;
	ret = malloc(sizeof(struct dfa_stat));
	if( ret == NULL )
		return NULL;
#ifdef DEBUG
	ret->id =id;
	id++;
#endif
	ret->set = set;
	if( dfa->start == NULL )
	{
		dfa->start = ret;
		ret->link.next = &ret->link;
		ret->link.prev = &ret->link;
	}
	else
		list_insert_before(&ret->link,&dfa->start->link);
	memset(&ret->table,0,256*sizeof(struct nfa_sat_set*));
	return ret;
}

/**
 * @brief This function travel from a nfa_stat,through all TRAN_FREE translate ,
 * to the equal nfa_stats it can access,and put them into set.
 * NOTE:this is a rescue funcion
 *
 * @param stat the start nfa_stat
 * @param set put all nfa_stats that equal to stat into set and return
 *
 * @return 0 if success,otherwise error. the reason maybe out of memory.
 */
static int stat_equal(struct nfa_stat *stat,struct nfa_stat_set *set)
{
	struct list *p;
	struct translate *trans;

	add_nfa_set(stat,set);
	p = stat->translates.next;
	while( p != &stat->translates )
	{
		trans = container_of( p,struct translate,link); 
		if( trans->type == TRAN_FREE )
		{
			if( add_nfa_set( trans->stat,set) != 0 )
				return -1;
			if( stat_equal(trans->stat,set) != 0 )
				return -1;
		}	
		p = p->next;
	}
	return 0;
}

static int set_equal(struct nfa_stat_set *set)
{
	struct list *p;
	p = set->head.next;
	while( p != &set->head )
	{
		if( stat_equal(container_of(p,struct nfa_stat_set_node,link)->stat,set) != 0 )
			return -1;
		p = p->next;
	}
	return 0;
}

/**
 * @brief A nfa_stat_set accept char c and change to a new nfa_stat_set
 *
 * @param set the source set
 * @param c accept the char c
 *
 * @return the new set after the source set accept a char,if the source set don't accept the 
 * char ,NULL will be return
 */
static struct nfa_stat_set* set_step(struct nfa_stat_set *set,unsigned char c)
{
	struct nfa_stat_set* ret = NULL;
	int i;
	struct nfa_stat *nfastat;
	struct list *p,*q;
	struct translate *trans;

	p = set->head.next;
	while( p != &set->head )
	{
		nfastat = container_of(p,struct nfa_stat_set_node,link)->stat;
		q = nfastat->translates.next;
		while( q != &nfastat->translates )
		{
			trans = container_of(q,struct translate,link);
			if( trans->type == TRAN_CHAR && trans->lo <= c && trans->hi >= c )
			{
				if( ret == NULL )
				{
					ret = malloc(sizeof(struct nfa_stat_set));
					if( ret == NULL )
						goto malloc_error;
					ret->num = 0;
					ret->head.next = &ret->head;
					ret->head.prev = &ret->head;
				}

				if(add_nfa_set(trans->stat,ret) != 0)
					goto mem_error;
			}
			q = q->next;
		}

		p = p->next;
	}
	return ret;
mem_error:
	free(ret);
malloc_error:
	return NULL;
}

/**
 * @brief compare whether two nfa_stat_set contain the same element
 *
 * @param s1
 * @param s2
 *
 * @return 0 if s1 and s2 are same,otherwise -1
 */
static int set_compare(struct nfa_stat_set *s1,struct nfa_stat_set *s2)
{
	struct list *p,*q;

	if( s1->num != s2->num )
	{
		return -1;
	}

	p = s1->head.next;
	q = s2->head.next;
	while( p != &s1->head && q != &s2->head )
	{
		if( container_of(p,struct nfa_stat_set_node,link)->stat != container_of(q,struct nfa_stat_set_node,link)->stat )
		{
			return -1;
		}
		p = p->next;
		q = q->next;
	}
	if( p == &s1->head && q == &s2->head )
	{
		return 0;
	}
	return -1;
}

static void set_free(struct nfa_stat_set *set)
{
	struct list *p,*save;
	p = set->head.next;
	while( p != &set->head )
	{
		save = p->next;
		list_delete(p);
		free(container_of(p,struct nfa_stat_set_node,link));

		p = save;
	}
	free(set);
}

/**
 * @brief Given a start dfa_stat,build it to a dfa.
 * it works like this:for a given dfa_stat,create all dfa_stats it can translate to,then for
 * the translated dfa_stats do the same procedure
 * NOTE:this is a rescue function
 *
 * @param dfa when complete,the dfa is return 
 * @param stat 
 *
 * @return 0 on success,-1 otherwise
 */
static int __nfa_to_dfa(struct dfa *dfa,struct dfa_stat *stat)
{
	int i;
	struct nfa_stat_set *set;
	struct list *p;

	for( i = 0;i < 256; i++ )
	{
		int dup = 0;
		set = set_step(stat->set,i);
		if( set == NULL )
			continue;

		if( set_equal(set) != 0)
			goto set_equal_error;

		p = &dfa->start->link;
		do
		{
			if(set_compare(container_of(p,struct dfa_stat,link)->set,set) == 0)
			{
				set_free(set);
				dup = 1;
				break;
			}

			p = p->next;
		}
		while( p != &dfa->start->link);

		if( dup == 1 )
		{
			stat->table[i] = container_of(p,struct dfa_stat,link);
		}
		else
		{
			stat->table[i] = alloc_dfa_stat(set,dfa);
			if( __nfa_to_dfa(dfa,stat->table[i]) != 0 )
				goto set_equal_error;
		}
	}
	return 0;
set_equal_error:
	free(stat);
mem_error:
	return -1;
}

struct dfa* nfa_to_dfa(struct nfa* nfa)
{
	struct dfa *dfa;
	struct nfa_stat_set *set;
	struct dfa_stat *start;
	int i = 0;
	struct list *p;

	if( nfa == NULL )
		goto exit;

	dfa = (struct dfa*)malloc(sizeof(struct dfa));
	if( dfa == NULL )
		goto exit;
	dfa->start = NULL;

	set = (struct nfa_stat_set*)malloc(sizeof(struct nfa_stat_set));
	if( set == NULL )
		goto mem_set_error;
	set->num = 0;
	set->head.next = &set->head;
	set->head.prev = &set->head;

	if( stat_equal(nfa->start,set) != 0 )
		goto nfa_set_error;

	start = alloc_dfa_stat(set,dfa);
	if( start == NULL )
		goto dfa_stat_error;

	if( __nfa_to_dfa(dfa,start) != 0 )
		goto dfa_error;

	return dfa;


dfa_error:
	//free dfa...
dfa_stat_error:
	free(start);
nfa_set_error:
	free(set);
mem_set_error:
	free(dfa);
exit:
	return NULL;
}

#ifdef DEBUG
void dfa_printf(struct dfa* dfa)
{
	struct dfa_stat *stat;
	struct list *p;
	int i;
	struct list *q;

	printf("--------------------debug info of dfa------------------------\n");
	assert(dfa);
	p = &dfa->start->link;
	do
	{
		stat = container_of(p,struct dfa_stat,link);
		if( stat->set->final != 0 )
		{
			printf(" final");
		}
		printf("\n");
		printf("stat id: %d,and it accepts\n",stat->id);
		for( i = 0 ; i < 256 ; i++ )
		{
			if( stat->table[i] != NULL )
			{
				printf("\t%c->%d ,",i,stat->table[i]->id);
			}
		}
		printf("\tnfa_set in this stat: ");
		q = stat->set->head.next;
		while( q != &stat->set->head )
		{
			printf("%d ",container_of(q,struct nfa_stat_set_node,link)->stat->id);
			q = q->next;
		}

		printf("\n");

		p = p->next;
	}
	while( p != &dfa->start->link );
}
#endif

static int __regex_match(struct dfa *dfa,const char *str)
{
	struct dfa_stat *active;

	active = dfa->start;
	while( *str != '\0' )
	{
		if( active->set->final == 1 )
			return 0;
		if( active->table[*str] != NULL )
		{
			active = active->table[*str];
			str++;
		}
		else
			return 1;
	}
	return 1;
}

char* regex_match(struct dfa *dfa,char *str)
{
	struct dfa_stat *active;
	char *ret;
	char *p;

	active = dfa->start;
	ret = str;
	while( *ret != '\0' )
	{
		if( __regex_match(dfa,ret) == 0 )
			return ret;
		ret++;
	}
	return NULL;
}

